|
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.〔Isaacs, R. "Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable." Amer. Math. Monthly 82, 221–239, 1975.〕 As snarks, the flower snarks are a connected, bridgeless cubic graphs with chromatic index equal to 4. The flower snarks are non-planar and non-hamiltonian. ==Construction== The flower snark J''n'' can be constructed with the following process : * Build ''n'' copies of the star graph on 4 vertices. Denote the central vertex of each star A''i'' and the outer vertices B''i'', C''i'' and D''i''. This results in a disconnected graph on 4''n'' vertices with 3''n'' edges (A''i''-B''i'', A''i''-C''i'' and A''i''-D''i'' for 1≤''i''≤''n''). * Construct the ''n''-cycle (B1... B''n''). This adds ''n'' edges. * Finally construct the ''2n''-cycle (C1... C''n''D1... D''n''). This adds ''2n'' edges. By construction, the Flower snark J''n'' is a cubic graph with 4''n'' vertices and 6''n'' edges. For it to have the required properties, ''n'' should be odd. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「flower snark」の詳細全文を読む スポンサード リンク
|